#include <cstdlib>
using namespace std;
#include <iostream>
#include <queue>
using namespace std;
/* 
二叉树使用二叉链表储存
设计算法判断结点p在哪一层
 */
struct TreeLinkNode
{
    int val;
    TreeLinkNode *left, *right, *next;
    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
/* 
使用特殊标记法的层序遍历实现，
在一层结束的时候，把一个特殊标记入队，用于标记一层已经结束了，
那么当这个特殊标记出队时，我就知道即将遍历到开始新一层的结点了
*/
void levelTraversal(TreeLinkNode *root)
{
    if (NULL == root)
        return;
    queue<TreeLinkNode *> myQueue;
    myQueue.push(root);
    // 根结点就是入对后代表一层结束插入特殊标记
    myQueue.push(NULL);
    int level = 1;
    while (!myQueue.empty())
    {
        TreeLinkNode *node = myQueue.front();
        myQueue.pop();
        if (NULL == node)
        {
            // 当特殊标记出队时意味着又一层结束啦
            if (myQueue.empty())
            {
                // 层结束时如果对列为空则说明已经遍历完了
                break;
            }
            level++;
            // 插入新的特殊标记代表下一层的开始
            myQueue.push(NULL);
            continue;
        }
        cout << "第" << level << "层结点:" << node->val << endl;
        if (NULL != node->left)
            myQueue.push(node->left);
        if (NULL != node->right)
            myQueue.push(node->right);
    }
}
int main()
{
    TreeLinkNode *root = new TreeLinkNode(1);
    TreeLinkNode *left = new TreeLinkNode(2);
    TreeLinkNode *right = new TreeLinkNode(3);
    TreeLinkNode *leftRight = new TreeLinkNode(4);
    TreeLinkNode *rightRight = new TreeLinkNode(5);
    root->left = left;
    root->right = right;
    left->right = leftRight;
    right->left = rightRight;
    levelTraversal(root);
    system("pause");
    return 0;
}
